package main

func QuickSortV2(nums []int) {
	if len(nums) <= 1 {
		return
	}
	QuickSortV2Core(nums, 0, len(nums)-1)
}

func QuickSortV2Core(nums []int, left, right int) {
	if left >= right {
		return
	}
	pivot := partitionV2(nums, left, right)

	QuickSortV2Core(nums, left, pivot-1)
	QuickSortV2Core(nums, pivot+1, right)
}

func partitionV2(nums []int, left int, right int) int {
	// 选择最左边元素做p
	p := nums[left]

	// 两个指针,两端同时找不符合条件的元素,交换 (先找右边)
	i, j := left, right
	for i < j {
		// 先从右边开始查找,不然两指针相遇时,会出现相遇值>pivot的情况
		for i < j && nums[j] >= p {
			j--
		}
		for i < j && nums[i] <= p {
			i++
		}
		// 交换不符合条件的元素
		nums[i], nums[j] = nums[j], nums[i]
	}
	// [left,i/j]都<=p  [i+1,right]都>=p

	// p要放到交界处
	nums[i], nums[left] = nums[left], nums[i]
	return i
}
